public class Solution464 {

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger>=desiredTotal){
            return true;
        }
        if ((1+maxChoosableInteger)*maxChoosableInteger/2<desiredTotal){
            return false;
        }
        int[] f=new int[1<<maxChoosableInteger];
        return dfs(0,0,maxChoosableInteger,desiredTotal,f);
    }

    private boolean dfs(int state, int now, int maxChoosableInteger, int desiredTotal,int[] f) {
        if (f[state]==0){
            boolean flag=false;
            for (int i=maxChoosableInteger;i>=1;i--){
                if ((state&(1<<(i-1)))==0){
                    if (now+i>=desiredTotal){
                        flag=true;
                        break;
                    }else {
                        flag|=!(dfs(state|(1<<(i-1)),now+i,maxChoosableInteger,desiredTotal,f));
                    }
                }
            }
            f[state]=flag?1:-1;
        }
        return f[state]==1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution464().canIWin(20,210));
    }
}
